// 排序

/**
 * 冒泡排序
 * 相邻的元素相互比较，存在较大元素的话，就交换相邻的元素的位置
 * 时间复杂度：O(n的2次方)
 * 空间复杂度:O(1)
 * 稳定排序
 * @param arr
 */
function bubbleSort(arr) {
    let exeCount = 0;
    for (let i = arr.length - 1; i > 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                let swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
            }
            exeCount++;
        }
    }
    return exeCount;
}

/**
 * 冒泡排序
 * 相邻的元素相互比较，存在较大元素的话，就交换相邻的元素的位置
 * 时间复杂度：O(n的2次方)
 * 空间复杂度:O(1)
 * 稳定排序
 * @param arr
 */
function bubbleSortWithFlag(arr) {
    let exeCount = 0;
    let swapFlag = false;
    for (let i = arr.length - 1; i > 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                let swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
                swapFlag = true;
            }
            exeCount++;
        }
        if (swapFlag) {
            swapFlag = false;
        } else {
            break;
        }
    }
    return exeCount;
}


/**
 * 选择排序
 * 每次找到最小（最大）值的索引，然后把他交换到前（后）面排好序的区域
 * 时间复杂度：O(n^2)
 * 空间复杂度: O(1)
 * 非稳定排序
 * @param arr
 */
function selectionSort(arr) {
    let exeCount = 0;
    for (let i = 0; i < arr.length - 1; i++) {
        let small = i;
        let j = i + 1;
        for (; j < arr.length; j++) {
            if (arr[small] > arr[j]) {
                small = j;
            }
            exeCount++;
        }
        if (small != i) {
            let tmp = arr[i];
            arr[i] = arr[small];
            arr[small] = tmp;
        }
    }
    return exeCount;
}

/**
 * 插入排序
 * 前面的区域是排好序，然后把元素插入到，排好序的区域合适的部分
 * 时间复杂度：O(n^2)
 * 空间复杂度: O(1)
 * 稳定排序
 * @param arr
 */
function insertionSortSlow(arr) {
    let exeCount = 0;
    for (let i = 1; i < arr.length; i++) {
        let tmp = arr[i]
        // 查找合适的位置
        let j = 0;
        for (; j < i; j++) {
            exeCount++;
            // 排好序的区域，从0开始，小到大
            if (tmp < arr[j]) {
                break;
            }
        }
        // 往后挪
        for (let k = i; k > j; k--) {
            arr[k] = arr[k - 1];
            exeCount++;
        }
        arr[j] = tmp;
    }
    return exeCount;
}

/**
 * 插入排序
 * 前面的区域是排好序，然后把元素插入到，排好序的区域合适的部分
 * 时间复杂度：O(n^2)
 * 空间复杂度: O(1)
 * 稳定排序
 * @param arr
 */
function insertionSort(arr) {
    let exeCount = 0;
    for (let i = 1; i < arr.length; i++) {
        let tmp = arr[i]
        // 查找合适的位置
        for (let j = i - 1; j >= -1; j--) {
            exeCount++;
            // 排好序的区域，从0开始，小到大
            if (tmp < arr[j]) {
                // 往后挪
                arr[j + 1] = arr[j];
            } else {
                arr[j + 1] = tmp;
                break;
            }
        }
    }
    return exeCount;
}

/**
 * 快速排序
 * 在数组中选出一个数字，把数组划分成2块，一块大于选中数字，一块小于选中数字，重复该过程。
 * 时间复杂度：O(n*log(n) )
 * 空间复杂度: O(n)
 * 非稳定排序
 * @param arr
 */
function quickSort(arr) {
    if (arr.length <= 0) {
        return 0;
    }
    let left = 0, right = arr.length - 1, selectIndex = 0;
    let middle = middleIndex(arr,left,right);
    swap(arr,selectIndex,middle);
    return quickSortPartion(arr, left, right, selectIndex);
}

function middleIndex(arr,start,end){
    if(start >= end){
        return start;
    }

    let winIndex = start;

    let startEle =  arr[start];
    let endEle =  arr[end];
    let middle = Math.floor((start+end)/2)
    let middleEle =  arr[middle];

    if( (startEle >=middleEle && endEle <= middleEle) ||  (startEle <=middleEle && endEle >= middleEle) ){
        return middle;
    }else if( (startEle <=middleEle &&  startEle >= endEle) ||  (startEle >=middleEle &&  startEle <= endEle)  ){
        return start;
    }else {
        return end;
    }

}

function swap(arr, from, to) {
    if(from==to){
        return
    }
    let tmp = arr[from];
    arr[from] = arr[to];
    arr[to] = tmp;
}

function quickSortPartion(arr, left, right, selectIndex) {
    if (left  >= right) {
        return 0;
    }
    let count = 0;

    let base = arr[selectIndex];
    let leftCursor = left;
    let rightCursor = right;
    let eqNum = 0;
    while (leftCursor < rightCursor) {
        // 找到小于等于基准数字的元素(必须现在第一位执行，防止leftCursor指向的元素大于基准值的索引)
        while (arr[rightCursor] >= base && leftCursor < rightCursor) {
            rightCursor--;
            count++;
            if(arr[rightCursor] == base ){
                eqNum++;
            }
        }
        // 找到大于基准数字的元素
        while (arr[leftCursor] <= base && leftCursor < rightCursor) {
            leftCursor++;
            count++;
        }

        if (leftCursor < rightCursor) {
            swap(arr, leftCursor, rightCursor);
        }
    }
    if(eqNum == (right - left )){
        // 优化点：检查数组里面的元素是否都相等
        return count;
    }
    swap(arr, selectIndex, leftCursor);

    // 获取区间的中间值
    let middle = middleIndex(arr,left,leftCursor - 1);
    // 交换位置
    swap(arr,left,middle);
    let leftCount = quickSortPartion(arr, left, leftCursor - 1, left);

    // 获取区间的中间值
    middle = middleIndex(arr,leftCursor + 1,right);
    // 交换位置
    swap(arr,leftCursor + 1,middle);
    let rightCount = quickSortPartion(arr, leftCursor + 1, right, leftCursor + 1);
    return count + leftCount + rightCount;
}
